package org.example.l0;

import org.example.l2.CharHelper;
import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

public class exist {
    @Test
    void aa() {
        char[][] from = CharHelper.from("[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\n");
        boolean abcced = exist(from, "ABCCED");
        System.out.println(abcced);
    }


    int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    int rows, cols, wordLen;
    char[][] board;
    String word;

    public boolean exist(char[][] board, String word) {
        if (board == null || (rows = board.length) == 0 || (cols = board[0].length) == 0 || word == null || (wordLen = word.length()) == 0) {
            return false;
        }

        this.board = board;
        this.word = word;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean[][] visited = new boolean[rows][cols];
                if (dfs(0, i, j, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    boolean dfs(int k,
                int row,
                int col,
                boolean[][] visited) {
        char v = board[row][col];
        if (word.charAt(k) != v) {
            return false;
        }
        k++;
        if (k == wordLen) {
            return true;
        }

        visited[row][col] = true;

        for (int[] ints : direction) {
            int row2 = row + ints[0], col2 = col + ints[1];
            if (row2 < 0 || row2 >= rows || col2 < 0 || col2 >= cols) {
                continue;
            }

            if (visited[row2][col2]) {
                continue;
            }

            visited[row2][col2] = true;
            boolean dfs = dfs(k, row2, col2, visited);
            if (dfs) {
                return true;
            }

            visited[row2][col2] = false;
        }

        visited[row][col] = false;
        k--;

        return false;
    }
}
